package Graph;


import java.util.*;

public class GraphByMatrix {
    private char [] arrayV;
    private int [][] matrix;
    private boolean isDirect;
    private HashMap<Character,Integer> indexMap;
    class Edge{
        int src;
        int dest;
        int weight;

        public Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }
    public GraphByMatrix(char[] array,int size , boolean isDirect){
        matrix = new int[size][size];
        this.isDirect = isDirect;
        for (int i = 0; i < size; i++) {
            Arrays.fill(matrix[i],Integer.MAX_VALUE);
        }
        initArrayV(array);
    }

    public void initArrayV(char []array){
        indexMap = new HashMap<>();
        arrayV = new char[array.length];
        for (int i = 0; i < array.length; i++) {
            arrayV[i] = array[i];
            indexMap.put(arrayV[i],i);
        }

    }
    public void addEdge(char srcV, char destV ,int weight){
        int s_index = indexMap.get(srcV);
        int v_index = indexMap.get(destV);
        matrix[s_index][v_index] = weight;
        if(!isDirect) {
            matrix[v_index][s_index] = weight;
        }
    }
    public void printGraph(){
        System.out.print("  ");
        for (int i = 0; i < arrayV.length; i++) {
            System.out.print(arrayV[i]+" ");
        }
        System.out.println();
        for (int i = 0; i < matrix.length; i++) {
            System.out.print(arrayV[i]+" ");
            for (int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j] == Integer.MAX_VALUE){
                    System.out.print("∞ ");
                }else {
                    System.out.print(matrix[i][j]+" ");
                }
            }
            System.out.println("");
        }

    }
    public int getDevOfV(char v){
        int count = 0;
        // 出度
        int v_index = indexMap.get(v);
        for (int i = 0; i < matrix.length; i++) {
            if(matrix[v_index][i] != Integer.MAX_VALUE) {
                count++;
            }
        }
        if(isDirect){
            for (int i = 0; i < matrix[0].length; i++) {
                if(matrix[i][v_index] != Integer.MAX_VALUE){
                    count++;
                }
            }
        }
        return count;
    }
    public  void bfs(char v){
        boolean [] tmp = new boolean[arrayV.length];
        Queue<Integer> queue = new LinkedList<>();
        int v_index = indexMap.get(v);
        queue.add(v_index);
        tmp[v_index] = true;
        while(!queue.isEmpty()){
            int poll = queue.poll();
            System.out.print(arrayV[poll]+"->");
            for (int i = 0; i < arrayV.length; i++) {
                if(matrix[poll][i] != Integer.MAX_VALUE && !tmp[i]){
                    queue.add(i);
                    tmp[i] = true;
                }
            }
        }
    }
    public  void dfs(char v){
        boolean[] visited  = new boolean[arrayV.length];
        int index_v = indexMap.get(v);
        visited[index_v] = true;
        System.out.print(arrayV[index_v]+"-> ");
        for (int i = 0; i < arrayV.length; i++) {
            if(matrix[index_v][i] != Integer.MAX_VALUE && !visited[i]){
                dfs(arrayV[i]);
            }
        }
    }
    public int kruskal(){
        int sum = 0;
        GraphByMatrix minTree = new GraphByMatrix(arrayV,arrayV.length,false);
        sum = kruskal_helper(minTree);
        return sum;
    }
    public void addEdgeByIndex(int src,int dest,int weight){
        matrix[src][dest] = weight;
        if(!isDirect) {
            this.matrix[src][dest] = weight;
        }

    }
    public int kruskal_helper(GraphByMatrix minTree){
        int size = matrix.length;
        PriorityQueue<Edge> queue = new PriorityQueue<>(((o1, o2) -> o1.weight - o2.weight));
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if(i < j && matrix[i][j]!= Integer.MAX_VALUE){
                    queue.add(new Edge(i,j,matrix[i][j]));
                }
            }
        }
        UnionFindSet UFSet = new UnionFindSet(matrix.length);
        int sum = 0;
        int n = 0;
        while(n < size -1 && !queue.isEmpty()){
            Edge poll = queue.poll();
            if(UFSet.isInSameSet(poll.dest,poll.src)){
                UFSet.union(poll.src,poll.dest);
                char dest_ = arrayV[poll.dest];
                char src_ = arrayV[poll.src];
                System.out.printf("把 %c%c权值为%d的边 加入到 最小生成树中\n",dest_,src_,matrix[poll.src][poll.dest]);
                minTree.addEdgeByIndex(poll.src,poll.dest,matrix[poll.src][poll.dest]);
                n++;
                sum += matrix[poll.src][poll.dest];
            }
        }
        minTree.printGraph();

        return sum;

    }
    public int prime(GraphByMatrix minTree ,char V){
        int v_index = indexMap.get(V);
        int totalWeight = 0;
        int size = 0;
        HashSet<Integer>setX = new HashSet<>();
        HashSet<Integer> setY = new HashSet<>();
        PriorityQueue<Edge> queue = new PriorityQueue<>((o1,o2)->o1.weight-o2.weight);
        setX.add(v_index);
        for (int i = 0; i < arrayV.length; i++) {
            if(matrix[v_index][i] != Integer.MAX_VALUE && !setX.contains(i) ){
                Edge edge = new Edge(v_index, i, matrix[v_index][i]);
                queue.add(edge);
            }

        }
        for (int i = 0; i < arrayV.length; i++) {
            if(!setX.contains(i)){
                setY.add(i);
            }
        }
        while(size < arrayV.length -1 &&!queue.isEmpty()){
            Edge edge = queue.poll();

            if(!setX.contains(edge.dest) ){

                System.out.printf("把 %c%c权值为%d的边 加入到 最小生成树中\n",arrayV[edge.src],arrayV[edge.dest],matrix[edge.src][edge.dest]);
                minTree.matrix[edge.src][edge.dest] = edge.weight;
                totalWeight += edge.weight;
                size++;

                for (int i = 0; i < arrayV.length; i++) {
                    if(!setX.contains(i) && matrix[edge.dest][i] != Integer.MAX_VALUE){
                        Edge edge1 = new Edge(edge.dest, i, matrix[edge.dest][i]);
                        queue.add(edge1);
                    }
                }
                setX.add(edge.dest);
                setY.remove(edge.dest);
            }
        }

        return totalWeight;

    }
    public void dijkstra(int [] dist,int []pPath,char src){
        boolean []visited = new boolean[arrayV.length];
        Arrays.fill(dist,Integer.MAX_VALUE);
        int u = indexMap.get(src);
        dist[u] = 0;
        int n = arrayV.length;

        for (int k = 0; k < n; k++) {

            int min = Integer.MAX_VALUE;

            for (int i = 0; i < n; i++) {
                if(!visited[i] && dist[i] < min){
                    min = dist[i];
                    u = i;
                }
            }
           // dist[u] = min;
            visited[u] = true;
            pPath[u] = 0;

            for (int v = 0; v < n; v++) {
                if(!visited[v] && matrix[u][v] != Integer.MAX_VALUE && dist[v] > matrix[u][v] + dist[u]){
                    dist[v] = matrix[u][v] + dist[u];
                    pPath[v] = u;
                }
            }
        }
        printPath(pPath,dist,'S');
    }
    public void printPath(int [] pPath,int[]dist,char srcV){
        int srcI = indexMap.get(srcV);
        for (int i = 0; i < arrayV.length; i++) {
            List<Integer>path = new ArrayList<>();
            if(i != srcI){ // 不打印起始
                int j = i;
                while(j != srcI){
                    path.add(j);
                    j = pPath[j];
                }
                path.add(srcI);
            }
            Collections.reverse(path);
            for (int pos = 0; pos < path.size(); pos++) {
                System.out.print(arrayV[path.get(pos)]+"->");

            }
            System.out.println("路径长度为"+dist[i]);
        }
    }
    public void bellmanFord(int [] dist,int []pPath,char src){
        Arrays.fill(dist,Integer.MAX_VALUE);
        int src_index = indexMap.get(src);
        dist[src_index] = 0;
        pPath[src_index] = 0;
        int n = arrayV.length;

        for (int k = 0; k < n; k++) {
            for (int u = 0; u < n; u++) {
                for (int v = 0; v < n; v++) {
                    if(matrix[u][v]!=Integer.MAX_VALUE &&dist[u] + matrix[u][v] < dist[v]){
                        dist[v] = dist[u] + matrix[u][v];
                        pPath[v] = u;
                    }
                }
            }
        }
        printPath(pPath,dist,src);
    }

    public static void main(String[] args) {
        String str = "syztx";
        char[] array = str.toCharArray();
        int [] dist = new int[array.length];
        int [] pPath = new int[array.length];
        GraphByMatrix g = new GraphByMatrix(array,str.length(),true);
        g.addEdge('s', 't', 6);
        g.addEdge('s', 'y', 7);
        g.addEdge('y', 'z', 9);
        g.addEdge('y', 'x', -3);
        g.addEdge('z', 's', 2);
        g.addEdge('z', 'x', 7);
        g.addEdge('t', 'x', 5);
        g.addEdge('t', 'y', 8);
        g.addEdge('t', 'z', -4);
        g.addEdge('x', 't', -2);
        g.bellmanFord(dist,pPath,'s');



    }

    public static void main2(String[] args) {
        char []arrayV = new char[]{'S','Y','Z','T','X'};
        GraphByMatrix graphByMatrix = new GraphByMatrix(arrayV,arrayV.length,true);
        graphByMatrix.addEdge('S','T',10);
        graphByMatrix.addEdge('S','Y',5);
        graphByMatrix.addEdge('Y','T',3);
        graphByMatrix.addEdge('Y','X',9);
        graphByMatrix.addEdge('Y','Z',2);
        graphByMatrix.addEdge('Z','X',6);
        graphByMatrix.addEdge('Z','S',7);
        graphByMatrix.addEdge('T','Y',2);
        graphByMatrix.addEdge('T','X',1);
        graphByMatrix.addEdge('X','Z',4);
        int [] dis = new int[arrayV.length];
        int [] pPath = new int[arrayV.length];

        graphByMatrix.dijkstra(dis,pPath,'S');
        for(int x : dis){
            System.out.print(x+" ");
        }
    }


    public static void main1(String[] args) {
        char []arrayV = new char[]{'A','B','C','D','E','F','G'};
        GraphByMatrix graphByMatrix = new GraphByMatrix(arrayV,arrayV.length,false);
        GraphByMatrix minTree = new GraphByMatrix(arrayV,arrayV.length,false);

        graphByMatrix.addEdge('A','B',18);
        graphByMatrix.addEdge('A','C',20);
        graphByMatrix.addEdge('B','D',6);
        graphByMatrix.addEdge('C','D',19);
       // graphByMatrix.printGraph();
        //System.out.println(graphByMatrix.getDevOfV('A'));
        //System.out.println("");
        //graphByMatrix.bfs('A');
        //graphByMatrix.dfs('A');
        int ret = graphByMatrix.kruskal();
        System.out.println("权值为："+ret);
        int ans = graphByMatrix.prime(minTree,'A');
        System.out.println("权值为："+ans);
        minTree.printGraph();



    }
}
